//1.不修改原数组
class Solution {
public:
    int rob(vector<int>& nums) {
        int n =nums.size();
        if(n==1) 
            return nums[0];

        int cur_val = max(nums[0],nums[1]);
        int pre_val = nums[0];
       
        for(int i=2;i<n;++i) {
            int temp =cur_val;
            cur_val = max(cur_val, pre_val + nums[i]);
            pre_val = temp;
        }
        return cur_val;
    }
};

//2.修改原数组
class Solution {
public:
    int rob(vector<int>& nums) {
        int n =nums.size();
        if(n==1) 
            return nums[0];

       
        nums[1]=max(nums[1],nums[0]);
       
        for(int i=2;i<n;++i) {
           nums[i] = max(nums[i-2] + nums[i], nums[i-1]);
        }
        return nums[n-1];
    }
};